%Notes:
% anytime a \begin{thing} is used, there needs to be a corresponding \end{thing}
% double quotes are done by using two single quotes

%states the different types of class
%article is being used because of the weird numbering system on the other
%classes, so titlepage has to explicitly stated in this class
\documentclass[titlepage]{article}

%this says to use times as a style and to indent the first paragraph because it 
%does not do that by default
\usepackage{times, indentfirst}

%this allows graphics to be added
\usepackage[pdftex]{graphicx}

%this package is to allow the following \restylefloat which is an override
%that allows the user to explicity state formatting with figures (images)
\usepackage{float}
\usepackage[T1]{fontenc}

\restylefloat{figure}

%the following three lines are all for the title and the various \huge, etc are different font
%sizes and there is a difference between \Huge and \huge
%\\* is the escape for new line
\title{\Huge CSE325 Lab 5 Memory Manager}
\author{\huge Group 4: \\*  \LARGE Matthew Cramer, Jesse Martinez, Marc Mendoza}
\date{\LARGE \today}

%needed to start the document, think of it like main in normal programming
\begin{document}
%creates the title page based on \title, \author, \date
\maketitle

%this labels a section and it will be numbered in the paper, there is a hierarchy to
%the levels of sections, and curly braces are required
\section{Introduction}
%text can be placed anywhere and it will show up when compiled

This lab creates a Memory Manager that will manage the Physical Memory and Backing Store(Hard Disk) space of an operating system.  In this documentation, an explanation will be given of how the Memory Manager will be utilized by the Testing Interface.  This includes a state diagram showing the states of a block of memory in the Memory Manager as well as a flow diagram of actions taken in the Memory Manager. To show how a page fault is handled, the Page-Replacement Algorithm is explained and how it works with the Backing Store. The documentation will also explain how the Physical Memory will be divided up between the System and Users.  It also explains the size of the Physical Memory and how the Physical Memory and Backing Store are represented in the Memory Manager.  Finally, test cases will be described to how we will test the program's functionality to ensure that the program is stable and works correctly.  

To run the Memory Manager, run the compile.sh script and then execute the ./run [input.txt] file that has an option to run a set of commands from a input file.  This is primary used for testing purposes from the testing program.

\section{Memory Manager}
The Memory Manager will work with the Testing Interface that supplies commands to it to perform different tasks in the manager.  When a page table is created by either the System or a User, the page table is allocated in Physical Memory in one frame and will be pointed to by an array keeping track of where the page tables are in Physical Memory. This array is stored in a frame in Physical Memory and will be used to locate the page tables quickly. Both the Physical Memory and Backing Store are queues implemented as linked lists.  For this reason, the manager can allocate as much memory as it needs for the process since the queue is implemented as a linked list.  This has the ability to keep track of the free list in memory and dequeue frames off the free list and enqueue into the Physical Memory list. This is a dynamic approach to allocating pages onto Physical Memory that way no empty frames are left unused since they are all connected by pointers. For page faults, the Least Recently Used algorithm is used to move pages in and out of Physical Memory from the linked list in Backing Store.  

\begin{figure}[H]
\begin{center}
\includegraphics[scale=.6]{Flowchart.jpg}
\caption{Flow chart for Memory Manager}
\end{center}
\end{figure}

The Memory Manager functions with a Testing Interface that will pass commands to the Memory Manager in order to allocate, deallocate, and create page faults. The memory manager will handle the commands that are meant for the manager, being the alloc\_pt, dealloc\_pt, and page\_fault commands. The Testing Interface will handle displaying the information for the user with the List function. Since the Testing Interface handles the arguments for the functions, the Memory Manager will assume that all information being passed to the Memory Manager is of correct type.  


\begin{figure}[H]
\begin{center}
\includegraphics[scale=.8]{MemoryState.jpg}
\caption{State Diagram for Memory}
\end{center}
\end{figure}

This state diagram is for a memory block only and all errors are handled by the Memory Manager. There are several states for a block of memory: unused, unallocated, allocated empty, allocated valid - page table, allocated valid - data, allocated To Be Evicted, and evicted. When the Memory Manager is initialized, all memory is initially in an unused state and then is initialized by the Memory Manager, putting the memory in the unallocated state. Memory is then allocated where two different actions can occur. In the first case, the allocated memory holds a created page table from which it will immediately enter the unallocated state once the System/User is done with that page table. The second case assigns data to the memory, placing it in the allocated valid data. Then the data can be unallocated or a page fault can occur causing the allocated memory to become selected for eviction, in preparation to be evicted. The memory is then evicted to Backing Store and enters the allocated empty state. Finally memory is terminated when all memory is freed from the unallocated state.

\subsection{Manager Actions}
The following is a list of commands that the Memory Manager receives from the Testing Interface that will operate in the program.

\subsubsection{init\_mem}
This function will initiate the Physical Memory and Backing store as linked lists that will contain a list of space being used and a free list.  Once both have been created, it will set variables indicating that the System will be able to use a max of 25\% for page tables and data and the rest for User page tables and data.

\subsubsection{list user | system | pagetable [page\_table\_id] }
The list function will simply return the structures that are associated with what is being requested. This could be page tables for a certain user of the system, or list all the structures in the Memory Manager.  This will be done by addressing the page table heads, which will be contained in a array stored in a frame in the Physical Memory,or data structure and return the frames to the Testing Interface. 

\subsubsection{alloc\_pt}
This function will allocate frames in Physical Memory for a new page table of the given argument that is the requested page table size.  It will first make sure the available space is there before creating the page table. If there is not, it will call upon the LRU algorithm to swap out memory for the page table. The program, for now, will determine if the page table is being requested by the System or a User.  This was done because it is not part of the Testing Interface and another manager will be sending the owner of the page table.  For now, the testing interface will request what ownership to give to the page table by asking the user to give it ownership.  Once the page table is created, it till be placed in memory and the page table location will be placed in an array that keeps track of where each page table is.  This array is stored in Physical Memory as one of the frames.

\subsubsection{dealloc\_pt}
This function will look to see if the given page table ID exists in Physical Memory. This is done by locating each page table in Physical Memory by addressing the array holding the valid pointers to the page tables. If it does, it will remove the page table from memory.  This will be done by moving the used frames from the Physical Memory list to the free list to be allocated again.

\subsubsection{page\_fault}
This function will search for the given page table ID and page to load the page into Physical Memory from Backing Store.  If there is no more room in memory, the function will call the Page-Replacement Algorithm to determine which frame to replace.  

\subsection{Page-Replacement Algorithm}
\subsubsection{Least Recently Used Algorithm}
For page replacement, the Least Recently Used algorithm (LRU) is used because it is a simple algorithm to implement it requires a counter in each frame.  The LRU algorithm does not suffer from the Belady's Anomaly as well. \


{\bf Proof:}

Given any reference string S = a1, a2, .., an. Let $ LRU_{i}$(S) be the number of faults that LRU incurs on S with a cache of size i,  show for all i and S, i$<$j,
\begin{center}
 $LRU_{i}$(S) $\geq$ $LRU_{i+1}$(S) $\geq$ $LRU_{i+2}$(S) $\geq$ ..$\geq$ $LRU_{j}$(S)
\end{center}
Defining that an array of size i can be embedded in another 
array list of size i+1, if the arrays are identical, 
except that the longer one has one more item, which is the last one.
 
\underline{Claim:} After each step of processing a sequence of requests, that an array of $LRU_{i}$ can be embedded in the array list of $ LRU_{i+1}$.

We prove the claim by induction on the number of steps:
\begin{enumerate}
\item
Basic case: if n=1, both $LRU_{i}$ and $LRU_{i+1}$ incur a fault and bring in $a_{1}$.
\item
Induction Hypothesis: the claim is true after step n.
\item 
To show it is also true after step n+1.
\begin{enumerate}
\item
Suppose before reading $a_{n+1}$ , $a_{n+1}$ is in the cache of $LRU_{i}$ (hit). According to IH, $a_{n+1}$ is also in the cache of $LRU_{i+1}$ (hit). Both moving $a_{n+1}$ to the beginning of their lists after reading $a_{n+1}$.  So the claim is also true after step  $a_{n+1}$.
\item
Suppose before reading $a_{n+1}$,$a_{n+1}$ is NOT in the cache of  $LRU_{i}$ (fault).
\begin{enumerate}
\item
$a_{n+1}$ is also not in the cache of $LRU_{i+1}$ (fault):both moving $a_{n+1}$  
to the beginning of their lists after reading $a_{n+1}$.  Claim holds.

\item
$a_{n +1}$ is in the cache of $LRU_{i+1}$ ($a_{n +1}$ must be the last page  
based on IH): $LRU_{i+1}$ moves its $a_{n +1}$  to the beginning of their 
lists after reading $a_{n +1}$. LRUi brings $a_{n +1}$ and replaces one of the 
old elements. By IH, all remaining items are same or evict page 
which is always at the end of list.
\end{enumerate}
\end{enumerate}
\end{enumerate}
The claim is proved. So at each step, if $LRU_{i+1}$ has a fault, then $LRU_{i}$ has a 
fault since $LRU_{i+1}$ list elements contain (embed) $LRU_{i}$ list elements.. So 
$LRU_{i}$(S) $\geq$  $LRU_{i+1}$(S). Finish proof for LRU.

Reference: http://ranger.uta.edu/~weems/NOTES5314/HW/hw3.3.pdf


\subsubsection{Backing Store Searching Algorithm}
To find the data to be placed back in Physical Memory with a page fault, the Memory Manager will need to know where the data is in Backing Store to retrieve.  When the LRU algorithm sends the index of the Least Recently used frame to the Memory Manger it will  move the data from the Physical Memory to Backing Store, it will keep track of where it gets placed in Backing store by the same method of how a page keeps reference to a page frame in Physical Memory.  If the frame has no reference for the data in Backing Store then it has not been loaded into Physical Memory yet.  If the page has been sent to Backing Store, the page table will hold that location but indicate that it is in Backing Store to reload if called upon.  

\subsection{Memory Manager Page/Frame Elements}

\begin{enumerate}
\item {\bf ID} 

The ID field of the frame will hold which page table/process this frame belongs to.  Since a process has its own unique ID and is creating a page table with that unique ID, every frame in memory or on the backing store will know which page table it belongs to.  The program will not check for unique ID names since that will be done by the Scheduler.

\item {\bf Index}
 
The index will keep track of where the frame is in Physical Memory or Backing Store.  Depending on if the Frame Type bit is indicating that this frame is in Physical Memory, it will be the location in the queue of the Physical Memory or in Backing Store if the Frame Type indicates it is in that state.  This bit is not actually recorded in the frame but rather just using the index at which the frame is at in the array.

\item {\bf Valid} 

This element will determine if the current frame is in use or not.  It will be NULL if the frame is not being used.  This will also be used by the Page Table to determine if the data has been brought into memory yet or not.  If it is valid, the block has been brought into Physical Memory at some point.  The block however may be in Backing Store and the other fields will indicate this.  

\item {\bf LRU} 

This field will hold the LRU counter will keep track of how long this page frame has been unused for since we are implementing the LRU Page-Replacement Algorithm.

\item {\bf Frame Type} 

This element will distinguish if a frame is in physical memory or backing store if it is in the page table but the memory block also has a frametype that determines if the frame is a pagetable or data.  This is used to help keep track of data and know what it is being used as.

\item {\bf Owner}

This element will hold the User ID for the page table and data that it is currently being used by.  This could either be a User or the System.

\item{\bf Page Table}

This field will be the array for the page table when assigned to a frame.  It will only be used for the page table when one is allocated and the other fields will not be used.  This was done to create both Physical Memory and Backing Store to contain the same type of memory block to hold data and to pass data more easily.   The Page table will be allocated to the maximum page table size but the ptsize field will hold how many frames the page table is holding.  This was done to statically create the page table array inside the memory block.  

The Page Table will be an array that holds the location in memory where the page is located for the particular page in the page table.  If the page in is Physical memory, it will point to the location in Physical Memory where that frame is.  If the page is in Backing Store, it will point to the location in Backing Store where the frame is.  The Frame Type bit will indicate if the index is in Physical Memory or Backing Store.  

\item{\bf ptsize}

This field will hold the size of the page table.  This number will be the number of frames in the page table.

\item{\bf data}

If the frame is a data frame being used by a page table, this field will hold the actual data that the process is using.  Since no processes are being implemented in the program yet, this field is just a place holder for now.  

\item{\bf nextIndex}

This field is used for the implementation of the linked list and will point to the next memory block in the list.

\item{\bf prevIndex}
 
This field is used for the implementation of the linked list and will point to the previous memory block in the list.  

\end{enumerate}

\subsection{Description of Memory Layout}
The Memory manager will be implemented with two types of memory: Physical Memory and Backing Store.  Each of these memory types will be as queues implemented as a linked list in the Memory Manager.  Each node in the linked list will be one frame size of 4KB.  

\subsubsection{Page Table}
For this implementation, the program can have a max of 16 page tables/processes that can be allocated.  Each page table will have a max of 1024 frames, or 4MB that can be allocted for a process. 4MB was chosen for the 16 processes that way we can ensure that Backing Store will never reach its capacity for this assignement and simplicity.  The page table will be placed in a block of memory and when a page fault occurs, and new block will be assigned to the linked list from the free list to be allocated for that page in the page table.  The Testing Interface will ensure that the maximum number of pages for a page table will be 1024.  

\subsubsection{Physical Memory}
Physical Memory will be 1MB, 256 frames, in size with a 4KB page size. The Physical Memory will be divided up between System/Kernel processes and data and User processes and data.  25\% of Physical Memory will be used for the System/Kernel and the other 75\% will be used for Users. For this reason, only 4 page tables can be allocated for the System and the other 12 for users.  This was chosen because we do not know how much memory the kernel will require but these numbers can change if needed.  If memory begins run out for the System or User, the Page-Replacement algorithm will begin to swap unused pages out. 

\subsubsection{Logical Memory}
As mentioned above, each page table will be given 4MB (1024 frames) of Logical Memory space to be used for the process. This number is static for now to ensure that each process gets a fair share about of memory to be used.  When a page table gets allocated in Physical Memory, the data for the process will be allocated in Backing Store as well using the algorithm mentioned above for the Page-Replacement policy.  This way there is a enough logical data used that it will overflow the Physical Memory and the Page-Replacement Algorithm will have to be used.  When a page fault is requested from the Testing Interface, the same algorithms will locate the requested page data to be placed in Physical Memory.  

\subsubsection{Backing Store}
Backing Store will be implemented with a 64MB capacity.  Each page in the backing store is also 4KB so therefore the backing store will have 16,384 frames/indices's.  The Backing Store will be implemented as a linked list and will contain a free list to add any data that gets enqueued to the Backing Store without having to locate free space. Each page table that is requested can have a maxiumum allocate 4MB of data in the Backing Storage that will be page faulted into Physical Memory when called upon when Physical Memory runs out of room.  

\subsection{Hardware}
In order to implement the Memory Manager certain hardware is required. The first piece of hardware is a counter so that the LRU algorithm can be implemented and keep track of the least used frame in Physical Memory. The second piece of hardware is hardware that can map a logical/virtual address to a physical address.  This will be done with a page table that is allocated with System access and used to translate the address. Without these pieces of hardware page faults would not occur and it would not be possible to access the backing storage in the Memory Manager.

\subsection{Run Time}
The run time of our memory manager is O(n). This is because a linear search may be done on the memory blocks in Physical Memory to search for the data to be replaced with the Page-Replacement algorithm. Since the pages in the page tables in Physical Memory will hold the location of the data for the process in Backing Store and Physical Memory, the system can go directly to the point where the data is located which is constant time. All other functions are constant since since a free list is implemented for both structures, requiring constant time to add frames to the linked lists without having to search for available space.  

\section {Testing Plan}
Tests were conducted by sending commands to the Memory Manager from a Testing program.  This testing program tested the capacity and integrity of the queues in the Memory Manager by expecting values back from the manager.  If the return values were what it expected, the test passed.  For the functionality of the Testing Interface, such as handling the user input and arguments for the commands, expected output samples were generated and compared with the actual output from the Testing Interface that are executed in the script file.  This was done by string comparison of the two output files in order to see if the correct output was given for each functionality test. The testing files are located in their own subfolder "TestingInterface/Tests".

To compile the Test program, run the "compileTests.sh" script and finally execute "runTests" to run the testing program.  The program will list the tests run and if they passed or not.  

\subsection {Capacity}
\subsubsection{Empty Memory}
This test will ensure that when the program starts, all memory in the program will be empty and will call the different list functions to ensure all the error statements are displayed correctly.  

\subsubsection{Max Memory}
This test will ensure that once the program starts up, there are no data in the either Physical Memory and Backing Store and then create the maximum number of page tables with the maximum page table size. This will ensure that the program can reach full capacity and that no more than the max number page tables with the max table size are created. All page tables will then be listed with the list command and will be checked to ensure no more than what is allowed by the max limits are allocated.

\subsubsection {Allocate Max Memory/Deallocate Memory}
This test will repeat the previous test and then deallocate page tables from memory by calling dealloc\_pt, this is to ensure that the correct page tables are deallocated and variables are reset properly. This will be done by listing all page tables when memory is maxed and then listing it again when memory is deallocated. Page tables will then be allocated to make sure we can still deallocate memory and then reallocate memory

\subsubsection {Allocate Max Memory/Deallocate All Memory}
This test will be to ensure that once the linked lists have maxed out with memory and then deallocate everything, that all variables are being reset properly and that memory continues to function properly.

\subsection {Functionality}
\subsubsection {init\_mem}
This test will ensure that when the program starts up, that this function must be called first to initiate the Physical Memory and Backing Store.  

\subsubsection{list}
This will ensure that when the list function is called, that it will list all user structures, all system data structures, and all defined page tables. If an argument is given, it will check to see if it is the right type of argument, being user, system, or page table [page\_table\_id].  If the argument is not a corresponding argument, it will report the error.  If it is, it will display the reserved data structures for the OS memory if system is the argument, data structures for user memory if the argument is user, and the associated page table if page table is the argument.  

\subsubsection{alloc\_pt page\_table\_size}
This test will make sure that a new page table is created in the memory with the proper page table size. Also it will check that all valid bits are properly set to indicate that memory spaces are being allocated and that all pages are properly referenced by the page table. 

\subsubsection{dealloc\_pt page\_table\_id}
This test will check that when a specific page table is deallocated, that the page table frames and all pages valid bits are set to false.

\subsubsection{page\_fault page\_table\_id page\_num}
This test will check that the LRU algorithm is working correctly and that memory is being swapped correctly (the page being moved is moved into Backing Store and that the needed page is moved to the Physical Memory). 

\section{Misc. Design Decisions}
\subsection{Page Size}
For this project, a page size of 4KB is used for the Physical Memory and Backing Store in order to have a frame take up an entire index of the queue. This was done so the pages cannot be divided into smaller amounts of memory to place smaller frames in.  With that page size and the number of frames in each memory, the Physical Memory comes out to be 1MB and Backing Store comes to be 64MB.  A page table will be placed inside a frame but use a logical space of 4MB max for data for the page table.  

\subsection{Page Table Size}
The maximum page table size is less than 4KB but has a logical memory of 4MB, that way the page table data can take up no more than 1024 frames in Physical Memory and Backing Store total.  This is to help control how much of the Physical Memory is being used and how much overflow will be placed in the Backing Store for a process so we do not overload the Backing Store with data as well.  This was also done to prevent page tables taking up a majority of the Physical Memory to give more room for data.

\subsection{Max Number of Page Tables}
To work with not overflowing the Backing Store, a maximum of 16 page tables/processes are allowed in the system to ensure that the page tables do not over run Physical Memory and the Logical Memory for each page table does not exceed the capacity of the Backing Store.  This was chosen to give an equal amount of processes to both the User and System.  Right now, the program will divide up the processes when called equally but for later implementation with other managers, they will assign who is allocating a page table.

\subsection{Unique PIDs}
Since the Scheduler is the manager that will be assignment PIDs to processes and ensure no duplicate IDs, the Memory Manager will assume that each page table being created is unique and will go on the assumption that it does not need to check for duplicate page tables.  

\subsection{Logical Memory}
4MB was assigned to each page table to use for process data due to the fact that we can overflow the Physical Memory to enable using the Page-Replacement Algorithm to test it.  Placing the data in Backing Store first when a page table is requested was done so the page fault function can be used easily to start moving data into memory to be used before having to call the Page-Replacement Algorithm to replace existing pages.

\subsection{Queue Manager}
We will be implementing the Physical Memory and Backing Store as linked lists and therefore will need to use the Queue Manager to handle enqueues, dequeues, and deletes from both structures.  The only changes that will be made is the PCB that will hold different elements now for this program as well as Delete now takes in the index to be deleted.  

\end{document}